P là tập hợp con của RP, và RP là tập hợp con của NP. Tương tự như vậy, P là tập hợp con của co-RP và co-RP là tập hợp con của co-NP. Hiện chưa biết các mối quan hệ tập hợp cha-con đó có chặt hay không. Tuy nhiên nếu giả thuyết phổ biến P = BPP là đúng thì RP, co-RP, và P đều bằng nhau.

Một ví dụ quan trọng của co-RP hiện vẫn chưa biết có nằm trong P không là kiểm tra đa thức không yêu cầu xác định xem một đa thức cho trước có đồng nhất bằng đa thức không hay không. Ví dụ, x·x − y·y − (x + y)·(x − y) là đa thức không trong khi x·x + y·y không phải.

Một định nghĩa khác của RP là lớp các bài toán giải được bằng máy Turing không đơn định trong đó máy chấp nhận khi và chỉ khi tỉ lệ số đường tính toán chấp nhận là ít nhất một hằng số. Trong khi đó, với lớp NP, máy chấp nhận khi có ít nhất một đường tính toán chấp nhận. Vì vậy RP rõ ràng là tập hợp con của NP.